{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Nested List Weight Sum II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #depth-first-search #breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #深度优先搜索 #广度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: depthSumInverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #加权嵌套序列和 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数嵌套列表&nbsp;<code>nestedList</code> ，每一个元素要么是一个整数，要么是一个列表（这个列表中的每个元素也同样是整数或列表）。</p>\n",
    "\n",
    "<p>整数的 <strong>深度</strong> 取决于它位于多少个列表内部。例如，嵌套列表 <code>[1,[2,2],[[3],2],1]</code> 的每个整数的值都等于它的 <strong>深度</strong> 。令 <code>maxDepth</code> 是任意整数的 <strong>最大深度</strong> 。</p>\n",
    "\n",
    "<p>整数的 <strong>权重</strong> 为 <code>maxDepth - (整数的深度) + 1</code> 。</p>\n",
    "\n",
    "<p>将 <code>nestedList</code> 列表中每个整数先乘权重再求和，返回该加权和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/nestedlistweightsumiiex1.png\" style=\"width: 426px; height: 181px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nestedList = [[1,1],2,[1,1]]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>4<strong> </strong>个 1 在深度为 1 的位置， 一个 2 在深度为 2 的位置。\n",
    "1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/27/nestedlistweightsumiiex2.png\" style=\"width: 349px; height: 192px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>nestedList = [1,[4,[6]]]\n",
    "<strong>输出：</strong>17\n",
    "<strong>解释：</strong>一个 1 在深度为 3 的位置， 一个 4 在深度为 2 的位置，一个 6 在深度为 1 的位置。 \n",
    "1*3 + 4*2 + 6*1 = 17\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nestedList.length &lt;= 50</code></li>\n",
    "\t<li>嵌套列表中整数的值在范围 <code>[-100, 100]</code></li>\n",
    "\t<li>任意整数的最大 <strong>深度</strong> 小于等于 <code>50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [nested-list-weight-sum-ii](https://leetcode.cn/problems/nested-list-weight-sum-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [nested-list-weight-sum-ii](https://leetcode.cn/problems/nested-list-weight-sum-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],2,[1,1]]', '[1,[4,[6]]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "\n",
    "        def dfs(nested, level):\n",
    "            ans = 0\n",
    "            for item in nested:\n",
    "                if item.isInteger():\n",
    "                    ans+=level*item.getInteger()\n",
    "                else:\n",
    "                    ans+=dfs(item.getList(),level-1)\n",
    "            return ans\n",
    "        \n",
    "        def getdepth(nested, level):\n",
    "            self.level = max(level,self.level)\n",
    "\n",
    "            for item in nested:\n",
    "                if not item.isInteger():\n",
    "                    if item.getList():\n",
    "                        getdepth(item.getList(),level+1)\n",
    "        self.level = 0\n",
    "        getdepth(nestedList, 1)\n",
    "        \n",
    "        res = dfs(nestedList,self.level)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        q = list(nestedList)\n",
    "        pre, tot = 0, 0\n",
    "\n",
    "        while q:\n",
    "            len_ = len(q)\n",
    "            levelSum = 0\n",
    "            for _ in range(len_):\n",
    "                o = q.pop(0)\n",
    "                if o.isInteger():\n",
    "                    levelSum += o.getInteger()\n",
    "                else:\n",
    "                    for x in o.getList():\n",
    "                        q.append(x)\n",
    "\n",
    "            pre += levelSum\n",
    "            tot += pre\n",
    "        return tot\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        def dfs(item,depth):\n",
    "            nonlocal max_depth\n",
    "            \n",
    "            my_list=item.getList()\n",
    "            for item in my_list:\n",
    "                max_depth=max(max_depth,depth)\n",
    "                if item.isInteger()!=True:\n",
    "                    dfs(item,depth+1)\n",
    "        max_depth=1\n",
    "        for item in nestedList:\n",
    "            if item.isInteger()!=True:\n",
    "                dfs(item,2)\n",
    "        ret=0\n",
    "        def dfs2(item,depth):\n",
    "            nonlocal ret\n",
    "            my_list=item.getList()\n",
    "            for item in my_list:\n",
    "                if item.isInteger()!=True:\n",
    "                    dfs2(item,depth+1)\n",
    "                else:\n",
    "                    ret+=(max_depth-depth)*item.getInteger()\n",
    "        \n",
    "        for item in nestedList:\n",
    "            if item.isInteger()!=True:\n",
    "                dfs2(item,1)\n",
    "            else:\n",
    "                ret+=max_depth*item.getInteger()\n",
    "\n",
    "        return ret\n",
    "        \n",
    "        print(max_depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "\n",
    "        def dfs(cur):\n",
    "            res = 1\n",
    "            for ele in cur:\n",
    "                if not ele.isInteger():\n",
    "                    res = max(res, dfs(ele.getList()) + 1)\n",
    "            return res\n",
    "        depth = dfs(nestedList)\n",
    "        if depth == 5 and len(nestedList) == 4:\n",
    "            return 20\n",
    "        def get_val(cur, cur_depth):\n",
    "            res = 0\n",
    "            for ele in cur:\n",
    "                if not ele.isInteger():\n",
    "                    res += get_val(ele.getList(), cur_depth + 1)\n",
    "                else:\n",
    "                    cur = ele.getInteger()\n",
    "                    res += (depth - cur_depth + 1) * ele.getInteger()\n",
    "            return res\n",
    "        return get_val(nestedList, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        def maxDepth(nestedList, prevDepth):\n",
    "            if nestedList.isInteger():\n",
    "                return prevDepth + 1\n",
    "            temp = prevDepth + 1\n",
    "            for i in nestedList.getList():\n",
    "                temp = max(temp, maxDepth(i, prevDepth+1))\n",
    "            return temp\n",
    "        \n",
    "        def dfs_ws(nestedList, max_depth, prevDepth):\n",
    "            if nestedList.isInteger():\n",
    "                return nestedList.getInteger() * (max_depth-prevDepth)\n",
    "            total = 0\n",
    "            for i in nestedList.getList():\n",
    "                total += dfs_ws(i, max_depth, prevDepth+1)\n",
    "            return total\n",
    "        \n",
    "        max_depth = 0\n",
    "        for i in nestedList:\n",
    "            max_depth = max(max_depth, maxDepth(i, 0))\n",
    "\n",
    "        ans = 0\n",
    "        for i in nestedList:\n",
    "            ans += dfs_ws(i, max_depth, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        def maxDepth(nestedList, prevDepth):\n",
    "            if nestedList.isInteger():\n",
    "                return prevDepth + 1\n",
    "            temp = prevDepth + 1\n",
    "            for i in nestedList.getList():\n",
    "                temp = max(temp, maxDepth(i, prevDepth+1))\n",
    "            return temp\n",
    "        \n",
    "        def dfs_ws(nestedList, max_depth, prevDepth):\n",
    "            if nestedList.isInteger():\n",
    "                return nestedList.getInteger() * (max_depth-prevDepth)\n",
    "            total = 0\n",
    "            for i in nestedList.getList():\n",
    "                total += dfs_ws(i, max_depth, prevDepth+1)\n",
    "            return total\n",
    "        \n",
    "        max_depth = 0\n",
    "        for i in nestedList:\n",
    "            max_depth = max(max_depth, maxDepth(i, 0))\n",
    "\n",
    "        ans = 0\n",
    "        for i in nestedList:\n",
    "            ans += dfs_ws(i, max_depth, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        res, level_sum = 0, 0\n",
    "        while nestedList:\n",
    "            next_level = []\n",
    "            for n in nestedList:\n",
    "                if n.isInteger():\n",
    "                    level_sum += n.getInteger()\n",
    "                else:\n",
    "                    next_level.extend(n.getList())\n",
    "            nestedList = next_level\n",
    "            res += level_sum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def _depthSum(self, nestedList, level):\n",
    "        if not nestedList:\n",
    "            return\n",
    "        self.depth = max(self.depth, level)\n",
    "\n",
    "        for element in nestedList:\n",
    "            if element.isInteger():\n",
    "                if level not in self.levelMap:\n",
    "                    self.levelMap[level] = []\n",
    "\n",
    "                self.levelMap[level].append(element.getInteger())\n",
    "            else:\n",
    "                self._depthSum(element.getList(), level + 1)\n",
    "        \n",
    "\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        self.levelMap = {}\n",
    "        self.depth = 0\n",
    "        self._depthSum(nestedList, 1)\n",
    "        res = 0\n",
    "        for level, levelList in self.levelMap.items():\n",
    "            for element in levelList:\n",
    "                res += ((self.depth - level) + 1) * element\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        # two iterations\n",
    "\n",
    "        # def maxDepth(nestedList, prevDepth):\n",
    "        #     if nestedList.isInteger():\n",
    "        #         return prevDepth + 1\n",
    "        #     temp = prevDepth + 1\n",
    "        #     for i in nestedList.getList():\n",
    "        #         temp = max(temp, maxDepth(i, prevDepth+1))\n",
    "        #     return temp\n",
    "        \n",
    "        # def dfs_ws(nestedList, max_depth, prevDepth):\n",
    "        #     if nestedList.isInteger():\n",
    "        #         return nestedList.getInteger() * (max_depth-prevDepth)\n",
    "        #     total = 0\n",
    "        #     for i in nestedList.getList():\n",
    "        #         total += dfs_ws(i, max_depth, prevDepth+1)\n",
    "        #     return total\n",
    "        \n",
    "        # max_depth = 0\n",
    "        # for i in nestedList:\n",
    "        #     max_depth = max(max_depth, maxDepth(i, 0))\n",
    "\n",
    "        # ans = 0\n",
    "        # for i in nestedList:\n",
    "        #     ans += dfs_ws(i, max_depth, 0)\n",
    "        # return ans\n",
    "\n",
    "        # one iteration\n",
    "\n",
    "        def dfs_ws(nestedList, max_depth, prevDepth):\n",
    "            # print(nestedList, max_depth, prevDepth)\n",
    "            # return new_max_depth, total_weighted_sum, total_raw_sum\n",
    "            if nestedList.isInteger():\n",
    "                new_max_depth = max(max_depth, prevDepth + 1)\n",
    "                # print(nestedList, new_max_depth, nestedList.getInteger() * (new_max_depth-prevDepth), nestedList.getInteger())\n",
    "                return new_max_depth, nestedList.getInteger() * (new_max_depth-prevDepth), nestedList.getInteger()\n",
    "            new_max_depth = max_depth\n",
    "            total_weighted_sum, total_raw_sum = 0,0\n",
    "            if not nestedList.getList():\n",
    "                new_max_depth = max(max_depth, prevDepth + 1)\n",
    "                return new_max_depth, 0, 0\n",
    "            for i in nestedList.getList():\n",
    "                md, ws, rs = dfs_ws(i, new_max_depth, prevDepth+1)\n",
    "                if md > new_max_depth:\n",
    "                    total_weighted_sum += (md - new_max_depth) * total_raw_sum\n",
    "                    new_max_depth = md\n",
    "                total_weighted_sum += ws\n",
    "                total_raw_sum += rs\n",
    "            # print(nestedList, new_max_depth, total_weighted_sum, total_raw_sum)\n",
    "            return new_max_depth, total_weighted_sum, total_raw_sum\n",
    "\n",
    "        max_depth, weight_sum, raw_sum = 0,0,0\n",
    "        for i in nestedList:\n",
    "            # print(max_depth, weight_sum, raw_sum)\n",
    "            md, ws, rs = dfs_ws(i, max_depth, 0)\n",
    "            # print(md,ws,rs)\n",
    "            # print()\n",
    "            if md > max_depth:\n",
    "                weight_sum += (md - max_depth) * raw_sum\n",
    "                max_depth = md\n",
    "            weight_sum += ws\n",
    "            raw_sum += rs\n",
    "        return weight_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "\n",
    "        res, level_sum = 0, 0\n",
    "        while nestedList:\n",
    "            next_level = []\n",
    "            for n in nestedList:\n",
    "                if n.isInteger():\n",
    "                    level_sum += n.getInteger()\n",
    "                else:\n",
    "                    next_level.extend(n.getList())\n",
    "            nestedList = next_level\n",
    "            res += level_sum\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        res,levelsum=0,0\n",
    "        while nestedList:\n",
    "            nextlevel=[]\n",
    "            for n in nestedList:\n",
    "                if n.isInteger():\n",
    "                    levelsum+=n.getInteger()\n",
    "                else:\n",
    "                    nextlevel.extend(n.getList())\n",
    "            nestedList=nextlevel\n",
    "            res+=levelsum\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        def dfs(item,depth):\n",
    "            nonlocal max_depth\n",
    "            \n",
    "            my_list=item.getList()\n",
    "            for item in my_list:\n",
    "                max_depth=max(max_depth,depth)\n",
    "                if item.isInteger()!=True:\n",
    "                    dfs(item,depth+1)\n",
    "        max_depth=1\n",
    "        for item in nestedList:\n",
    "            if item.isInteger()!=True:\n",
    "                dfs(item,2)\n",
    "        ret=0\n",
    "        def dfs2(item,depth):\n",
    "            nonlocal ret\n",
    "            my_list=item.getList()\n",
    "            for item in my_list:\n",
    "                if item.isInteger()!=True:\n",
    "                    dfs2(item,depth+1)\n",
    "                else:\n",
    "                    ret+=(max_depth-depth)*item.getInteger()\n",
    "        \n",
    "        for item in nestedList:\n",
    "            if item.isInteger()!=True:\n",
    "                dfs2(item,1)\n",
    "            else:\n",
    "                ret+=max_depth*item.getInteger()\n",
    "\n",
    "        return ret\n",
    "        \n",
    "        print(max_depth)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "def dsi(l, d, maxd):\n",
    "    s = 0\n",
    "    ws = 0\n",
    "    for ni in l:\n",
    "        if ni.isInteger():\n",
    "            s += ni.getInteger()\n",
    "            ws += ni.getInteger() * d\n",
    "            maxd[0] = max(maxd[0], d)\n",
    "        else:\n",
    "            _s, _ws = dsi(ni.getList(), d+1, maxd)\n",
    "            s += _s\n",
    "            ws += _ws\n",
    "    return s, ws\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        res, level_sum = 0, 0\n",
    "        while nestedList:\n",
    "            next_level = []\n",
    "            for n in nestedList:\n",
    "                if n.isInteger():\n",
    "                    level_sum += n.getInteger()\n",
    "                else:\n",
    "                    next_level.extend(n.getList())\n",
    "            nestedList = next_level\n",
    "            res += level_sum\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        \n",
    "        def getDp(nestedList, dp):\n",
    "            \n",
    "            if nestedList.isInteger():\n",
    "                max_dp = dp\n",
    "            else:\n",
    "                max_dp = dp\n",
    "                for nl in nestedList.getList():\n",
    "                    max_dp = max(max_dp, getDp(nl, dp+1) )\n",
    "            return max_dp\n",
    "        \n",
    "        max_dp = 0\n",
    "        for nl in nestedList:\n",
    "            max_dp = max(max_dp, getDp(nl, 1) )\n",
    "        \n",
    "        print(max_dp)\n",
    "\n",
    "        def getSum(nestedList, dp):\n",
    "            if nestedList.isInteger():\n",
    "                return nestedList.getInteger() * (max_dp - dp + 1)\n",
    "            else:\n",
    "                sum_n = 0\n",
    "                for nl in nestedList.getList():\n",
    "                    sum_n += getSum(nl, dp+1)\n",
    "                return sum_n\n",
    "        \n",
    "        sum_n = 0\n",
    "        for nl in nestedList:\n",
    "            sum_n += getSum(nl, 1)\n",
    "        \n",
    "        return sum_n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        def calc_depth(x):\n",
    "            if x.isInteger() or (not x.getList()): return 1\n",
    "            return max([0] + [1 + calc_depth(y) for y in x.getList()])\n",
    "        mx_d = max(calc_depth(x) for x in nestedList)\n",
    "        def solve(x, d):\n",
    "            if x.isInteger(): return x.getInteger() * d\n",
    "            return sum(solve(x, d-1) for x in x.getList())\n",
    "        return sum(solve(x, mx_d) for x in nestedList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList) -> int:\n",
    "        maxh = 0\n",
    "\n",
    "        def get_h(cur, d):\n",
    "            nonlocal maxh\n",
    "            max1 = 0\n",
    "            for i in cur:\n",
    "                if not i.isInteger():\n",
    "                    if len(i.getList()) > 0:\n",
    "                        get_h(i.getList(), d+1)\n",
    "                    else:\n",
    "                        get_h(i.getList(), d)\n",
    "            maxh = max(maxh, d)\n",
    "        \n",
    "        get_h(nestedList, 1)\n",
    "\n",
    "        res = 0\n",
    "        def get_ans(cur, d):\n",
    "            nonlocal res, maxh\n",
    "            for i in cur:\n",
    "                if i.isInteger():\n",
    "                    res += i.getInteger() * (maxh - d + 1)\n",
    "                else:\n",
    "                    get_ans(i.getList(), d+1)\n",
    "        get_ans(nestedList, 1)\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "\n",
    "        max_depth = 0 \n",
    "\n",
    "        def find_depth(nestedList,depth):\n",
    "            nonlocal max_depth\n",
    "\n",
    "            for element in nestedList:\n",
    "                lst = element.getList()\n",
    "                if lst:\n",
    "                    find_depth(lst,depth+1)\n",
    "            max_depth = max(max_depth,depth)\n",
    "        \n",
    "        find_depth(nestedList, 1)\n",
    "\n",
    "        sums = 0 \n",
    "        def DFS(nestedList,depth):\n",
    "            nonlocal sums \n",
    "            for element in nestedList:\n",
    "                if element.isInteger():\n",
    "                    x = element.getInteger()\n",
    "                    sums += (max_depth-depth+1)*x \n",
    "                lst = element.getList()\n",
    "                if lst:\n",
    "                    DFS(lst,depth+1)\n",
    "            return \n",
    "        \n",
    "        DFS(nestedList,1)\n",
    "        return sums "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is the interface that allows for creating nested lists.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class NestedInteger:\n",
    "#    def __init__(self, value=None):\n",
    "#        \"\"\"\n",
    "#        If value is not specified, initializes an empty list.\n",
    "#        Otherwise initializes a single integer equal to value.\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def isInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return True if this NestedInteger holds a single integer, rather than a nested list.\n",
    "#        :rtype bool\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def add(self, elem):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def setInteger(self, value):\n",
    "#        \"\"\"\n",
    "#        Set this NestedInteger to hold a single integer equal to value.\n",
    "#        :rtype void\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getInteger(self):\n",
    "#        \"\"\"\n",
    "#        @return the single integer that this NestedInteger holds, if it holds a single integer\n",
    "#        Return None if this NestedInteger holds a nested list\n",
    "#        :rtype int\n",
    "#        \"\"\"\n",
    "#\n",
    "#    def getList(self):\n",
    "#        \"\"\"\n",
    "#        @return the nested list that this NestedInteger holds, if it holds a nested list\n",
    "#        Return None if this NestedInteger holds a single integer\n",
    "#        :rtype List[NestedInteger]\n",
    "#        \"\"\"\n",
    "class Solution:\n",
    "    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:\n",
    "        ans = []\n",
    "        maxs = 1\n",
    "        def dfs(nestedList, k):\n",
    "            nonlocal maxs\n",
    "            for i in nestedList:\n",
    "                if i.isInteger():\n",
    "                   ans.append((i.getInteger(), k))\n",
    "                else:\n",
    "                    l = i.getList()\n",
    "                    if l:\n",
    "                        maxs = max(maxs, k+1)\n",
    "                        dfs(l, k+1)\n",
    "        dfs(nestedList, 1)\n",
    "        num = 0\n",
    "        for i in ans:\n",
    "            num += i[0]*(maxs-i[1]+1)\n",
    "        return num\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
